import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wx
 * Date: 2024-04-21
 * Time: 23:46
 */
public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }


    //public TreeNode root

    /**
     * 创建一颗二叉树,创建成功返回根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;
    }

    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void preorderTraversal(TreeNode root) {
        if(root == null){
            return ;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }



    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.val + " ");
        inOrder(root.right);
    }
    public void inOrderTraversal(TreeNode root) {
        if(root == null){
            return ;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(cur.val + " ");
            cur = top.right;
        }
    }

    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val + " ");
    }

    public void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null ||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.println(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = cur.right;
            }
        }
    }

    public int nodeSize = 0;

    int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }

    int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
    }

    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);

    }

    // 获取第K层节点的个数
    int getKLevelNodeCount (TreeNode root,int k){
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    int getHeight (TreeNode root){
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? rightHeight +1 : leftHeight + 1;
    }
    int getHeight2 (TreeNode root){
        if (root == null) {
            return 0;
        }

        return getHeight2(root.left) > getHeight2(root.right) ? getHeight2(root.left) +1 : getHeight2(root.right) + 1;
    }
    // 检测值为value的元素是否存在
    TreeNode find (TreeNode root,char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }

        TreeNode ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }

        TreeNode ret2 = find(root.right, val);
        if (ret2 != null) {
            return ret2;
        }

        return null;
    }
    //层序遍历
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree (TreeNode root){
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;//结束循环
            }
        }
        //需要判断队列当中 是否有非空元素
        while(!queue.isEmpty()){
            TreeNode tep = queue.peek();
            if (tep == null) {
                queue.poll();
            }else {
                return false;
            }
        }
        return false;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.abs(leftHeight - rightHeight) <= 1 &&
                isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight (TreeNode root){
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight
                ?  leftHeight + 1:
                rightHeight +1;
    }


    void levelOrder(TreeNode root) {
        if (root == null) {
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");

            if (cur.left == null) {
                queue.offer(cur.left);
            }
            if (cur.right == null) {
                queue.offer(cur.right);
            }
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size != 0){
                TreeNode cur = queue.poll();
//                System.out.print(cur.val + " ");
                tmp.add(cur.val);
                size--;
                if (cur.left == null) {
                    queue.offer(cur.left);
                }
                if (cur.right == null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }

    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public class Main {

        public  int i = 0;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);

            while(in.hasNextLine()){
                String str = in.nextLine();

                TreeNode root = creatTreeNode(str);

                inOrder(root);
            }
        }
        public static TreeNode creatTreeNode(String str) {
            // 1.遍历字符串
            TreeNode root = null;
            int i = 0;
            if(str.charAt(i) != '#'){
                // 2.根据中序遍历创建字符串
                root = new TreeNode(str.charAt(i));
                i++;
                root.left = creatTreeNode(str);
                root.right = creatTreeNode(str);
            }else{
                i++;
            }
            // 3.返回字符串
            return root;
        }

        public static void inOrder(TreeNode root) {
            if(root == null) {
                return ;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);

        }
    }








//    /**
//     * 把前序遍历的结果存到内存当中
//     * @param root
//     * @return
//     */
//
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//
//        if (root == null) {
//            return list;
//        }
//        list.add(root.val);
//        List<Integer> leftTree = preorderTraversal(root.left);
//        list.addAll(leftTree);
//        List<Integer> rightTree = preorderTraversal(root.right);
//        list.addAll(rightTree);
//        return list;
//    }


}
